package com.tang.algorithm.swordFingerOffer;



import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author tlm
 * @version 1.0
 * @date 2020/4/22 10:41
 * 重建二叉树
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * <p>
 *  
 * <p>
 * 例如，给出
 * <p>
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 * 返回如下的二叉树：
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 *  
 * <p>
 * 限制：
 * <p>
 * 0 <= 节点个数 <= 5000
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
 */
public class RebuildBinaryTree {
    public static void main(String[] args) {
        System.out.println("==============================二叉树的遍历==============================");
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        treeNode1.left = null;
        treeNode1.right = treeNode2;
        treeNode2.right = null;
        treeNode2.left = treeNode3;
        treeNode3.left = null;
        treeNode3.right = null;
        List<Integer> list = preorderTraversal(treeNode1);
        System.out.println("前序遍历的结果为：");
        list.forEach(System.out::print);
        System.out.println();
        List<Integer> list2 = inorderTraversal(treeNode1);
        System.out.println("中序遍历的结果为：");
        list2.forEach(System.out::print);
        System.out.println();
        List<Integer> list3 = postorderTraversal(treeNode1);
        System.out.println("后序遍历的结果为：");
        list3.forEach(System.out::print);
        System.out.println("==============================重建二叉树==============================");
        int preorder[] = {3, 9, 20, 15, 7};
        int inorder[] = {9, 3, 15, 20, 7};
        TreeNode treeNode = buildTree(preorder, inorder);

    }

    /**
     * 重构二叉树
     *
     * @param preorder 前序遍历结果
     * @param inorder  中序遍历结果
     * @return
     */
    static TreeNode buildTree(int[] preorder, int[] inorder) {
        //处理数组长度为0的情况
        if (preorder.length == 0) {
            return null;
        }
        int rootVal = preorder[0];
        //处理数组长度为1的情况
        if (preorder.length == 1) {
            return new TreeNode(rootVal);
        }
        //确定root的位置
        TreeNode root = new TreeNode(rootVal);
        //确定左子树和右子树的范围
        int rootIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }
        //递归，假设root的左右子树都已经构建完毕，那么只要将左右子树安到root左右即可
        //注意Arrays.copyOfRange(int[],start,end)是[)的区间
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, rootIndex + 1), Arrays.copyOfRange(inorder, 0, rootIndex));
        root.right = buildTree(Arrays.copyOfRange(preorder, rootIndex + 1, preorder.length), Arrays.copyOfRange(inorder, rootIndex+1, inorder.length));

        return root;
    }



    /**
     * 二叉树的前序遍历
     *
     * @param root
     * @return
     */
    public static List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        preorder(root, list);

        return list;
    }

    static void preorder(TreeNode root, List<Integer> list) {
        if (root != null) {
            list.add(root.val);
            preorder(root.left, list);
            preorder(root.right, list);
        }
    }

    /**
     * 二叉树的中序遍历
     *
     * @param root
     * @return
     */
    public static List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        inorder(root, list);

        return list;
    }

    static void inorder(TreeNode root, List<Integer> list) {
        if (root != null) {
//            if(root.left!=null){
            inorder(root.left, list);
//            }
            list.add(root.val);
//            if(root.right!=null){
            inorder(root.right, list);
//            }

        }
    }

    /**
     * 二叉树的后遍历
     *
     * @param root
     * @return
     */
    public static List<Integer> postorderTraversal(TreeNode root) {

        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        postorder(root, list);

        return list;
    }

    static void postorder(TreeNode root, List<Integer> list) {
        if (root != null) {
//            if(root.left!=null){
            postorder(root.left, list);
//            }
//            if(root.right!=null){
            postorder(root.right, list);
//            }
            list.add(root.val);

        }
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

